package com.starview.star.compiler.util;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Stack;

public class TopologySort<T>
{
  private final Stack<Pair<Integer, IDefinition<T>>> stack = new Stack<Pair<Integer, IDefinition<T>>>();
  private final List<IDefinition<T>> definitions;
  private final List<List<IDefinition<T>>> groups = new ArrayList<List<IDefinition<T>>>();

  public TopologySort(Collection<? extends IDefinition<T>> defs)
  {
    definitions = new ArrayList<IDefinition<T>>(defs);
  }

  private int analyseRefs(IDefinition<T> def, int point)
  {
    int low = point;

    for (T ref : def.references())
      low = minPoint(low, analyse(ref, low));

    return low;
  }

  private int analyse(T ref, int low)
  {
    // Is the reference already being considered?
    for (int ix = stack.size() - 1; ix >= 0; ix--) {
      IDefinition<T> entry = stack.get(ix).right();

      if (entry.defines(ref))
        return minPoint(low, stack.get(ix).left());
    }

    // Look for an implementation
    for (IDefinition<T> def : definitions) {
      if (def.defines(ref))
        return minPoint(low, analyseDef(def));
    }

    return low;
  }

  private static int minPoint(int X, int Y)
  {
    if (X <= Y)
      return X;
    return Y;
  }

  private int analyseDef(IDefinition<T> def)
  {
    int low = stack.size();
    definitions.remove(def);
    stack.push(Pair.pair(low, def));

    int point = analyseRefs(def, low);

    if (point == low) {
      // We have a group
      List<IDefinition<T>> group = new ArrayList<IDefinition<T>>();
      while (!stack.isEmpty()) {
        Pair<Integer, IDefinition<T>> entry = stack.peek();
        if (entry.left() >= point) {
          group.add(entry.right());
          stack.pop();
        } else
          break;
      }
      if (!group.isEmpty())
        groups.add(group);
    }
    return point;
  }

  public List<List<IDefinition<T>>> sort()
  {
    while (!definitions.isEmpty()) {
      analyseDef(definitions.get(0));
    }
    return groups;
  }

  public interface IDefinition<T>
  {
    boolean defines(T obj);

    Collection<T> references();
  }
}
